本篇同步發布於Blog: [解題] LeetCode - 1047 Remove All Adjacent Duplicates In String

平台：

LeetCode

題號：

1047 - Remove All Adjacent Duplicates In String

題目連結：

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/

題目說明：

        輸入1個字串，只要有相鄰2個字元是相同的，則把這2個字元移除。移除後的字串要再確認是否有相鄰2個字元相同，繼續重複移除的動作，直到沒再移除為止。

        比如範例輸入的abbaca，一開始移除bb，變成aaca，再移除aa，最後剩下ca為答案

解題方法：

   　使用一個堆疊Stack，從字串的左邊開始掃描，Stack的Top會紀錄目前最新的字元，如果下1個字元和Top一樣，則Top要移除掉，否則都一直加進Stack。

最後Stack反轉的字串則為答案。

比如範例輸入abbaca

1. 第1個字元是a, Stack空的, 加入Stack變成[a]
2. 第2個字元是b, Stack top(a)和b不同, 加入Stack變成[a,b]
3. 第3個字元是b, Stack top(b)和b相同, Stack pop後變成[a]
4. 第4個字元是a, Stack top(a)和a相同, Stack pop變成[]
5. 第5個字元是c, Stack空的, 加入Stack變成[c]
6. 第6個字元是a, Stack top(c)和a不同, 加入Stack變成[c,a]

從Stack的Top往下Pop的順序是a => c,  反轉成 c => a 則為答案。

難度為Easy

程式碼 (C++ 與 C#)：

class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> st;
        for(int i = 0 ; i < S.length();++i){
            if(st.empty() || st.top() != S[i]){
                st.push(S[i]);
            }
            else{
                st.pop();
            }
        }
        
        string ans = "";
        while(!st.empty()){
            ans += st.top();
            st.pop();
        }
        
        reverse(ans.begin(), ans.end());
        
        return ans;
    }
};

public class Solution {
    private static string ReverseString(string s)
    {
        char[] array = s.ToCharArray();
        Array.Reverse(array);
        return new string(array);
    }
    
    public string RemoveDuplicates(string S) {
        Stack<char> st = new Stack<char>();
        for(int i = 0 ; i < S.Length;++i){
            if(st.Count == 0 || st.Peek() != S[i]){
                st.Push(S[i]);
            }
            else{
                st.Pop();
            }
        }
        
        StringBuilder ans = new StringBuilder();
        while(st.Count > 0){
            ans.Append(st.Peek());
            st.Pop();
        }
        
        return ReverseString(ans.ToString());
    }
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/1000-1099/1047.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/1000-1099/1047.cs